﻿using System;
using System.Collections.Generic;
using System.Text;

namespace CSharpAlgorithm
{
    public class Diamond2
    {
        public Diamond2()
        {
            int testCase = Convert.ToInt16(Console.ReadLine());
            for (int i = 0; i < testCase; i++)
            {
                int maxWidth = Convert.ToInt16(Console.ReadLine());
                int[,] item = new int[maxWidth, maxWidth];

                for (int j = 0; j < maxWidth * 2 - 1; j++)
                {
                    string[] tokens = Console.ReadLine().Split(' ');

                    int x = (j >= maxWidth) ? maxWidth - 1 : j;
                    int y = (j >= maxWidth) ? j - maxWidth + 1 : 0;

                    for (int k = 0; k < tokens.Length; k++)
                    {
                        item[x, y] = Convert.ToInt16(tokens[k]);
                        item[x, y] = Math.Max(
                            item[x, y] + ((y > 0) ? item[x, y - 1] : 0),
                            item[x, y] + ((x > 0) ? item[x - 1, y] : 0)
                            );

                        x--; y++;
                    }
                }
                Console.WriteLine(item[maxWidth - 1, maxWidth - 1]);
            }
        }
    }
}
